package com.study;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-14 10:36
 * @version: 1.0
 * @description: 柠檬水找零
 * 每杯柠檬水售价五元，顾客排队购买，一次买一杯，只能向你付 5、10、20元，每个顾客必须正确找零，
 * 一开始手里没有任何零钱
 * 贪心算法：先保证局部求最优解,从而达到整体最优
 **/
public class LemonChange {
    public static void main(String[] args) {
        System.out.println(change(new int[]{5,5,10,10,5,20}));
    }

    private static boolean change(int[] numbers) {
        // 定义变量 记录 五元 和 十元 数量
        int five = 0,ten = 0;
        for (int number : numbers) {
            if (number == 5){
                five++;
            }else if(number == 10){
                if (five > 0){
                    five--;
                    ten++;
                }else {
                    return false;
                }
            }else {
                if (five > 0 && ten > 0){
                    five--;
                    ten--;
                }else if (five >= 3){
                    five -= 3;
                }else {
                    return false;
                }
            }
        }
        return true;
    }

    private static boolean change1(int[] numbers){
        // 定义几个遍历存钱
        int five = 0,ten = 0;
        for (int number : numbers) {
            if (number==5){
                five++;
            }else if (number == 10){
                if (five>0){
                    five--;
                    ten++;
                }else {
                    return false;
                }
            }else {
                if (five > 0 && ten > 0){
                    five--;
                    ten--;
                }else if(five >= 3){
                    five -= 3;
                }else {
                    return false;
                }
            }
        }
        return true;
    }
}
